\section{Implementação}

Neste trabalho é apresentada uma implementação do algoritmo ACO para solução do
problema de seleção de características, escrita na linguagem C. A variação do ACO
proposta utiliza elitismo, herança de soluções anteriores, atualização de feromônios
local e global, e opcionalmente, o auxílio de uma busca local. A implementação
utiliza a abordagem tipo filtro para avaliação das soluções durante a otimização
e um classificador é utilizado para avaliar a solução final. 

A implementação do ACO deste trabalho possui os seguintes parâmetros: número de formigas,
tamanho da elite, habilitar busca local, $\alpha$, $\beta$, porcentagem de evaporação de
feromônio, taxa de feromônio inicial e número máximo de avaliações de solução. Os parâmetros 
$\alpha$ e $\beta$ são utilizados para ponderar a influência da trilha de feromônio e do
conhecimento heurístico local na fase de construção de solução.

Os passos do laço principal de otimização podem ser observados no algoritmo \ref{alg1}.

\begin{algorithm}[ht]\caption{ACOFS\label{alg1}}

    $elite \leftarrow 0$ \\
    $bestSol \leftarrow 0$ \\
    $h().eval \leftarrow  0$ \\

    \While{$(h().eval < MAX)$} {

        \ForEach{$(ant \; in \; Anthill)$} {
            $ant.sol \leftarrow  inherit(elite) $\\
            $ant.sol \leftarrow buildway(\alpha, \beta) $\\
            $ant.fitness \leftarrow h(ant.sol) $\\

            \If{$LOCAL\_SEARCH$} {
                $ant.sol \leftarrow localSearch()$ \\
			}
		}

        $rankAnts()$ \\
        $elite \leftarrow selElite()$ \\
        $updateBestSol(bestSol)$ \\
        $updateTrail()$ \\
	}

    $return \; bestSol$ \\


\end{algorithm}

%secoes sao na verdade paragrafos, portanto não separei mas deixei o texto comentado para 
%guiar a escrita...As seções seguintes serão dedicadas para descrever a representação das 
%informações, o detalhamento das funções de herança da elite, construção de caminho, 
%avaliacão da qualidade da solução, busca local e atualização do feromônio.

O programa recebe como entrada uma base de dados para treinamento e um valor referente a 
importância individual da característica na base. Além da matriz para representar a base 
e o vetor com a importância das característica, é mantida uma matriz quadrada de ferômonios 
com o tamanho igual ao número de características. Um vetor binário representa uma solução. 
Uma posição como o valor um indica que a respectiva característica foi selecionada e o valor 
zero que não foi.

A solução inicial de uma formiga começa com características herdadas das soluções que formam 
a elite da iteração anterior. Uma probabilidade de herança é definida, portanto para cada 
característica selecionada por uma das formigas que formam a elite na iteração anterior, existe 
uma probabilidade definida de essa característica ser herdada na solução de cada formiga na 
iteração atual. Na primeira iteração, não existe nenhuma característica selecionada na elite, 
portanto nenhuma característica é herdada e as soluções começam vazias.

Na fase de construção, novas características são selecionadas, complementando a solução herdada.
Os passos da fase de construção podem ser observados no algoritmo \ref{alg2}.
Uma função heurística de construção avalia a importância individual de uma característica 
considerando os valores na matriz de feromônio e o valor da característica no vetor de importância 
individual. Ao contrário da matriz de 
feromônio, que evolui durante o processo de otimização, o vetor de imoprtância individual das 
características permanece estático, com os valores obtidos utilizando a função chi-quadrao
\cite{} do framework weka \cite{}. 

\begin{algorithm}[ht]\caption{Buildway\label{alg2}}

	$v \leftarrow avgFeatureContribution(ant.sol)$ \\
	\For{$(i \leftarrow 0; i < nFeatures; i++)$} {
		$f \leftarrow nextFeature$ \\
		\If{$(hBuild(f, \alpha, \beta) > v$)} {
			$ant.sol[f] \leftarrow 1$ \\
			$localTrailUpdate(ant.sol)$ \\
			$v \leftarrow avgFeatureContribution(ant.sol)$ \\
		}
	}

\end{algorithm}

%talvez seja bom apresentar o pseudo codigo dessa parte local tambem
As características são analisadas em uma ordem pseudo-aleatória e são selecionadas se o valor 
da função heurística de construção é maior ou igual à média dos valores da mesma função para 
as características já selecionadas. Durante a fase de construção ocorre uma atualização local
da trilha de feromônios e isso deve afetar a construção da solução das formigas ainda na iteração atual.
A função heurística de construção é dada por $\alpha * avgTrail(f, ant.sol) + \beta * localHeuristic(f) $,
sendo \emph{f} a heurística candidata a seleção e \emph{avgTrail(f, ant.sol)} a média de feromônio na trilha formada
pelas características já selecionadas da formiga e \emph{f}.

O processo de busca local tem como objetivo conseguir melhoras de forma rápida com pequenas 
modificações. A busca sempre avança quando encontra uma melhora e termina imediatamente 
quando nenhuma das três possibilidades de modificação causa melhora na solução. As três 
modificações são:

\begin{enumerate}
	\item remover uma característica existente;
    \item adicionar uma nova característica; 
	\item trocar uma característica, ou seja, remover uma e adicionar outra.
\end{enumerate}

As características para remoção, adição ou troca são definidas aleatoriamente. A função utilizada
para avaliar as soluções durante a busca local é a mesma utilizada na avaliação para a atualização 
de feromônios.

A implementação utiliza uma abordagem do tipo filtro, a função heurística utilizada na busca 
local e na avaliação das soluções para atualização da matriz de feromônios é a distância extra-classe(REFERENCIAR DISSERTACAO). 

% Lucas pode explicar melhor essa parte e REFERENCIAR a dissertacao que a prof passou


%depois de falar das distancia das classes:
Após a avaliação da qualidade das soluções de cada formiga, elas são organizadas em odem não 
decrescente. As formigas melhores colocadas formam o conjunto de elite. Apenas as formigas do 
conjunto elite atualizam a matriz de feromônios. A quantidade de feromônio depositado depende
da colocação da formiga no conjunto elite e da relação da qualidade de sua solução e da melhor 
solução encontrada até o momento. Imediatamente após o deposito do feromônio, ocorre a evaporação. 
O tamanho do conjunto elite foi definido como 10\%  da quantidade total de formigas e a taxa de 
evaporação foi fixada em 5\%. 

A matriz de feromônios é inicializada com valores próximos a 0.15, com uma pequena variação 
aleatória. Os valores da trilha variam entre 0 e 1. Na fase de autalização da trilha de 
feromônio, o valor calculado por cada formiga do conjunto elite para depósito é inserido nas 
entradas relacionadas da matriz. Para cada característica selecionada \emph{i}, a 
\emph{i}-ésima linha da matriz é atualizada nas \emph{j}-ésimas colunas, para cada característica 
\emph{j} selecionada simultâneamente a característica \emph{i}.

% Na apresentacao podemos fazer uma matriz e mostrar um exemplo

O número de avaliações utilizando a função heurística do tipo filtro é contabilizado. Quando esse 
valor atinge o valor máximo configurado, o processo de otimização termina e a melhor solução é 
retornada. 

% Lucas pode falar sobre a avaliacao da solucao final utilizando weka e naivebayes 
